package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Arrays;
import java.util.Scanner;

/*
有n项工作,每项工作分别在si时间开始,在ti时间结束.
对于每项工作,你都可以选择参与与否.如果选择了参与,那么自始至终都必须全程参与.
此外,参与工作的时间段不能重复(即使是开始的瞬间和结束的瞬间的重叠也是不允许的).

你的目标是参与尽可能多的工作,那么最多能参与多少项工作呢?

1 ≤ n ≤ 100000

1 ≤ si ≤ ti ≤ 10^9

输入:
第一行:n
第二行:n个整数空格隔开,代表n个工作的开始时间
第三行:n个整数空格隔开,代表n个工作的结束时间

样例输入:
5
1 3 1 6 8
3 5 2 9 10

样例输出:
3
	（说明:选取工作1,3,5；选择3个工作）
 */
public class c区间调度by贪心也叫不重叠区间 {
	public static void main(String[] args) {
		c区间调度by贪心也叫不重叠区间 test = new c区间调度by贪心也叫不重叠区间();
		test.useGreedyAlgorithm1();
	}
	
	public void useGreedyAlgorithm1() {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] start = new int[n];
		int[] terminate = new int[n];
		Job[] jobs = new Job[n];
		for (int i = 0; i < n; i++) {
			start[i] = scanner.nextInt();
		}
		for (int i = 0; i < n; i++) {
			terminate[i] = scanner.nextInt();
		}
		for (int i = 0; i < n; i++) {
			jobs[i] = new Job(start[i], terminate[i]);
		}
		Arrays.sort(jobs);
		int res = GreedyAlgorithm1(n, jobs);
		System.out.println(res);
	}
	
	public int GreedyAlgorithm1(int n, Job[] jobs) {
		int count = 1;//默认可选工作数=1；因为最不济，工作都冲突，你还可以从中选择一个
		int current = jobs[0].terminate;//贪心，必须从最先开始的工作，开始找起。
		for (int i = 1; i < n; i++) {//因为我们已经根据结束时间排序的，下面的if所以不会出现傻傻的错误
			if (jobs[i].start > current) {//碰到紧跟的下一个工作，并且不重叠
				count++;
				current = jobs[i].terminate;//更新current
			}
		}
		return count;
	}
	
	/**
	 * 创建私有内部类
	 * 把start和terminate打包
	 * 并且必须实现排序规则
	 * 我们的排序规则是：比较结束时间，结束时间在数轴上靠前的，排序就靠前
	 * @author wuqiu
	 */
	private static class Job implements Comparable<Job> {
		int start;
		int terminate;
		public Job(int start, int terminate) {
			this.start = start;
			this.terminate = terminate;
		}
		@Override
		/**
		this是新元素，other是老元素
		this.string.compareTo(other.string)会返回一个int A
		Suff类的compareTo会返回一个int,实际上就是把A返回
		在使用了自然排序的集合中添加Suff类对象
		这些对象的顺序是根据A决定的
		A = 0，在有些集合中，新元素(this)就不会加入；Array.sort不会导致“不加入”
		A > 0，this在other后面加入
		A < 0，this在other前面加入
	 */
		public int compareTo(Job o) {
			int x = this.terminate - o.terminate;
			if (x == 0) {//为了解决terminate相同的情况
				return this.start - o.start;//其实针对本题，这里this与o谁在前都可以，谁减谁都可以。
				//this减o，结果就是，t相同的情况下，哪个线段长，那么就排在前面
			}
			return x;
		}
	}
}
